package com.chapter6;

import java.util.*;
import java.util.Random;

public class RandomNumbers {
	List<Integer> sample;
	public static int randInt(int min, int max) {

	    // NOTE: Usually this should be a field rather than a method
	    // variable so that it is not re-seeded every call.
	    Random rand = new Random();
	    // nextInt is normally exclusive of the top value,
	    // so add 1 to make it inclusive
	    int randomNum = rand.nextInt((max - min) + 1) + min;
	    return randomNum;
	}
	
	private void swap(int[] A, int i, int j){
		int temp=A[i];
		A[i]=A[j];
		A[j]=temp;
	}
	public void getRandomSubarray(int[] A, int k){
		int n=A.length;
		int num=k;
		if(k>n/2)
			num=n-k;
		for(int i=0;i<num;i++){
			int rand=randInt(i,A.length);
			swap(A,i,rand);
		}
		if(k>n/2){
			for(int i=0;i<n/2;i++)
				swap(A,i,n-1-i);
		}
	}
	
	public void sampleOnlineData(int data,int k){
		if(sample==null){
			sample=new ArrayList<Integer>();
		}
		if(sample.size()<k)
			sample.add(data);
		else{
			int rand=randInt(0,k+1);
			if(rand!=k)
				sample.add(rand, data);
		}
	}
	
	public int binarySearch(double[] P, double rand){
		return binarySearchHelper(P,rand,0,P.length);
	}
	
	public int binarySearchHelper(double[] P, double rand, int min, int max){
		int mid=min+(max-min)/2;
		if(rand>P[mid] && rand<P[mid+1])
			return mid;
		else if(rand<P[mid])
			return binarySearchHelper(P,rand,min, mid);
		else
			return binarySearchHelper(P,rand,mid+1, max);
	}
	public double nonUniformNumber(double[] P, double[] T){
		//pre processing step
		for(int i=1;i<P.length;i++)
			P[i]=P[i]+P[i-1];
		double rand=randInt(0,100)/100;
		//do binary search for the number rand
		int index=binarySearch(P,rand);
		return T[index];
	}
}
